package com.tyrone.algorithm.graph;

/**
 * 闭环检测
 */
public class DirectedCycle {
    private boolean[] marked;       //索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean hasCycle;       // 记录图中是否有环
    private boolean[] onStack;      //索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上

    public DirectedCycle(Digraph G){
        marked=new boolean[G.V()];
        onStack=new boolean[G.V()];
        this.hasCycle=false;
        for (int v = 0; v < G.V(); v++) {
            if (!marked[v]){
                dfs(G,v);
            }
        }
    }


    /**
     * 基于深度优先搜索，检测图G中是否有环
     * @param G
     * @param v
     */
    private void dfs(Digraph G,int v) {
        marked[v]=true;
        onStack[v] =true;
        for (Integer w : G.adj(v)) {
            if (!marked[w]){
                dfs(G,w);
            }
            if (onStack[w]){
                hasCycle=true;
                return;
            }
        }
        onStack[v]=false;
    }

    /**
     * 判断图中是否有环
     * @return
     */
    public boolean hasCycle(){
        return hasCycle;
    }

}
